#include<bits/stdc++.h>

using namespace std;
// typedef pair<int , char> PIC;
template<typename T>
class Heap
{
public:
    Heap(int _capacity = 16)
    {
        data.reserve(_capacity + 1);
        capacity = _capacity;
    }
    Heap(const vector<T>& _data)
    {
        data.reserve(_data.size() + 1);
        capacity = _data.size();
        for(int i = 0 ; i < _data.size() ; ++i)
            data[i + 1] = _data[i];
        size = _data.size();
        heapify();
    }
    void push(T item)
    {
        if(size == capacity) reserve_capacity(capacity * 2);
        data[++size] = item;
        if(size > 1) up(size); 
    }
    T pop()
    {
        // try {
        //     if(size == 0) throw "Heap is empty";
        // catch(const char* msg) {
        // // 处理异常
        // cout << "Exception caught: " << msg << endl;
        // // 程序不会停止，黑框不会消失
        // }
        if(size == 0)
        {
            // throw "Heap is empty";
            cout<<"Heap is empty"<<endl;
        }
        T item;
        try 
        {
            item = data[1];
        }
        catch(const char* msg)
        {
            cout << "Exception caught: " << msg << endl;
        }
        data[1] = data[size--];
        down(1);
        if(size < capacity / 4 &&  capacity > 16) reserve_capacity(capacity / 2);
        return item;
    }
    T top() const
    {
        if(size == 0) throw "Heap is empty";
        return data[1];
    }
    bool is_empty() const 
    {
        return size == 0;
    }
    int heap_size() const
    {
        return size;
    }
    
private:
    vector<T> data;
    /// @brief 
    int size = 0;
    int capacity = 0;
    void heapify()
    {
        // for(int i = size ; i >= 1 ; --i) down(i);
        for(int i = size / 2 ; i >= 1 ; --i) down(i);
    }
    void up(int i)
    {
        while(i > 1)
        {
            int p = i / 2;//爹
            if(data[p] <= data[i]) break;
            //爹比儿子大
            swap(data[p] , data[i]);
            i = p;
        }
    }
    void down(int i)
    {
        while(2 * i <= size)
        {
            int j = 2 * i , right = j + 1;
            if(j + 1 <= size && data[j + 1] < data[j]) ++j;//找小儿子
            if(data[i] <= data[j]) break;//小儿子大于爹，跳过
            //
            swap(data[i] , data[j]);
            i = j;//跳到小儿子的index
        }
    }
    void reserve_capacity(int new_capacity)
    {
        data.reserve(new_capacity + 1);
        capacity = new_capacity;
    }
};

int main()
{
    //test
    vector<int> vec;
    for(int i = 10 ; i > 0 ; --i) vec.push_back(i);
    Heap<int> heap(vec);
    for(int i = 0 ; i < 12 ; ++i)
    {
        cout<<heap.pop()<<" "<<heap.heap_size()<<endl;
    }
    system("pause");
    return 0;
}